package leetcode.doublepointer;

//457. 环形数组是否存在循环
public class CircularArrayLoop {
    public static void main(String[] args) {

        int[] data = {2,-1,1,2,2};
        System.out.println(circularArrayLoop(data));
    }

    public static boolean circularArrayLoop(int[] nums){
        int n = nums.length;
        // 按照题意，起点seq[0]可能不从下标0开始
        for(int i = 0; i < n; ++i){
            int slow = i;
            int fast = next(nums,i,n);
            // 检查同向
            while(nums[fast] * nums[slow] > 0 && nums[next(nums,fast,n)] * nums[slow] > 0){
                if(fast == slow){
                    if(slow == next(nums,slow,n)) {
                        break; // 存在长度k为1的同向环
                    } else {
                        return true; // 否则满足要求
                    }
                }
                // 指针移动
                fast = next(nums,next(nums,fast,n),n);
                slow = next(nums,slow,n);
            }
        }

        return false;
    }
    private static int next(int[] nums,int i,int n){
        // 注意java下标不能像python有负数，-1需要处理成n-1
        return ((i + nums[i]) % n + n) % n;
    }

}
